package easy.demo03;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: wfmiss
 * @Date: 2023/12/13/8:45
 * @Description:
 * 题目来源：力扣 https://leetcode.cn/problems/merge-two-sorted-lists/
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */
public class mergeTwoLists {
    public static void main(String[] args) {
        /**
         * 测试用例：
         *示例 1：
         * 输入：l1 = [1,2,4], l2 = [1,3,4]
         * 输出：[1,1,2,3,4,4]
         *
         * 示例 2：
         * 输入：l1 = [], l2 = []
         * 输出：[]
         *
         * 示例 3：
         * 输入：l1 = [], l2 = [0]
         * 输出：[0]
         */
        ListNode listNode1 = new ListNode(-2);
        ListNode listNode2 = new ListNode(5);
        // ListNode listNode3 = new ListNode(3);
        // ListNode listNode4 = new ListNode(9);
        // ListNode listNode5 = new ListNode(9);
        // ListNode listNode6 = new ListNode(9);
        // ListNode listNode7 = new ListNode(9);
        listNode1.next = listNode2;
        // listNode2.next = listNode3;
        // listNode3.next = listNode4;
        // listNode4.next = listNode5;
        // listNode5.next = listNode6;
        // listNode6.next = listNode7;
        ListNode p = listNode1;
        while (p.next != null) {
            System.out.print(p.val);
            p = p.next;
        }
        System.out.println(p.val);

        ListNode listNode12 = new ListNode(-9);
        ListNode listNode22 = new ListNode(-6);
        ListNode listNode32 = new ListNode(-3);
        ListNode listNode42 = new ListNode(-1);
        ListNode listNode52 = new ListNode(1);
        ListNode listNode62 = new ListNode(6);
        listNode12.next = listNode22;
        listNode22.next = listNode32;
        listNode32.next = listNode42;
        listNode42.next = listNode52;
        listNode62.next = listNode62;
        ListNode p2 = listNode12;
        while (p2.next != null) {
            System.out.print(p2.val);
            p2 = p2.next;
        }
        System.out.println(p2.val);
        ListNode x =  mergeTwoLists(listNode1, listNode12);
        while (x.next != null) {
            System.out.print(x.val);
            x = x.next;
        }
        System.out.println(x.val);
    }
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 如果其中一个为null，则返回不为null的ListNode;都为null就随便返回一个
        if(list2==null||list1==null)return list1==null?list2:list2==null?list1:list2;
        // 将p1指针挪到list1尾部
        ListNode p1 = list1;
        while (p1.next!=null){
            p1=p1.next;
        }
        // 将list与list2首尾相连合并成一个ListNode
        p1.next=list2;
        // 再将p1指针指向list1首元素
        p1=list1;
        // 如果p1有没有下一个节点，则直接返回p1
        if (p1.next==null){
            return p1;
        }
        // 将p2指针指向p1的下一个节点
        ListNode p2=p1.next;
        // 将list1重新升序排序
        while (true){
            while (p2.next!=null){
                if (p1.val>p2.val){
                    p1.val+= p2.val;
                    p2.val= p1.val-p2.val;
                    p1.val-= p2.val;
                }
                p2=p2.next;
            }
            if (p1.val>p2.val){
                p1.val+= p2.val;
                p2.val= p1.val-p2.val;
                p1.val-= p2.val;
            }
            p1=p1.next;
            // 当p1指针移动到队尾时结束循环
            if (p1.next==null)break;
            p2=p1.next;
        }
        // 排序完成，返回list1
        return list1;
    }

}
